package com.cb2.algorithm.leetcode;

/**
 * <a href="https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/">二叉搜索树的最近公共祖先(Lowest Common Ancestor of a Binary Search Tree)</a>
 * <p>给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。</a>
 * <p><a href="https://baike.baidu.com/item/%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88/8918834?fr=aladdin">最近公共祖先的定义</a>为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1:
 *      输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
 *                                6
 *                             /    \
 *                            <a color='blue'>2</a>      <a color='blue'>8</a>
 *                           / \    / \
 *                          0   4  7   9
 *                             / \
 *                            3   5
 *      输出: 6
 *      解释: 节点 2 和节点 8 的最近公共祖先是 6。
 *
 * 示例 2:
 *      输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
 *                                6
 *                             /    \
 *                            <a color='blue'>2</a>      8
 *                           / \    / \
 *                          0   <a color='blue'>4</a>  7   9
 *                             / \
 *                            3   5
 *      输出: 2
 *      解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
 * </pre>
 * </p>
 * <p>
 * <b>说明:</b>
 * <ul>
 *     <li>所有节点的值都是唯一的。</li>
 *     <li>p、q 为不同节点且均存在于给定的二叉搜索树中。</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @see LC0235LowestCommonAncestorOfABinarySearchTree_M 二叉搜索树的最近公共祖先(Lowest Common Ancestor of a Binary Search Tree)
 * @see LC0236LowestCommonAncestorOfABinaryTree_M 二叉树的最近公共祖先(Lowest Common Ancestor of a Binary Tree)
 * @see LC1644LowestCommonAncestorOfBinaryTree_II_M 二叉树的最近公共祖先 II(Lowest Common Ancestor of a Binary Tree II)
 * @see LC1650LowestCommonAncestorOfBinaryTree_III_M 二叉树的最近公共祖先 III(Lowest Common Ancestor of a Binary Tree III)
 * @since 2023/5/16 9:52
 */
public class LC0235LowestCommonAncestorOfABinarySearchTree_M {

    static class Solution {
        /**
         * 二叉搜索树：左子树的节点值都小于根节点。右子树的节点值都大于根节点。
         */
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            //return lowestCommonAncestorByIterator(root, p, q);
            return lowestCommonAncestorByRecursion(root, p, q);
        }

        private TreeNode lowestCommonAncestorByIterator(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null || p == root || q == root) {
                return root;
            }
            while (root != null) {
                // p、q均在根节点的左侧
                if (root.val > p.val && root.val > q.val) {
                    root = root.left;
                }
                // p、q均在根节点的右侧
                else if (root.val < p.val && root.val < q.val) {
                    root = root.right;
                } else {
                    return root;
                }
            }
            return null;
        }

        private TreeNode lowestCommonAncestorByRecursion(TreeNode root, TreeNode p, TreeNode q) {
            if (root.val > p.val && root.val > q.val) {
                return lowestCommonAncestorByRecursion(root.left, p, q);
            } else if (root.val < p.val && root.val < q.val) {
                return lowestCommonAncestorByRecursion(root.right, p, q);
            }
            return root;
        }
    }


    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        TreeNode rootLeft = new TreeNode(5);
        TreeNode rootRight = new TreeNode(1);
        TreeNode rootLeftLeft = new TreeNode(6);
        TreeNode rootLeftRight = new TreeNode(2);
        TreeNode rootRightLeft = new TreeNode(0);
        TreeNode rootRightRight = new TreeNode(8);
        TreeNode rootLeftRightLeft = new TreeNode(7);
        TreeNode rootLeftRightRight = new TreeNode(4);

        root.left = rootLeft;
        root.right = rootRight;

        rootLeft.left = rootLeftLeft;
        rootLeft.right = rootLeftRight;
        rootRight.left = rootRightLeft;
        rootRight.right = rootRightRight;

        rootLeftRight.left = rootLeftRightLeft;
        rootLeftRight.right = rootLeftRightRight;

        Solution solution = new Solution();
        Printer.printTreeNode(solution.lowestCommonAncestor(root, rootLeft, rootRight));
        Printer.printTreeNode(solution.lowestCommonAncestor(root, rootLeft, rootLeftRightRight));
    }
}